package LeetCode.题库.困难;

/**
 * @author 挚爱之夕
 * @version 1.0
 * @implSpec 给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
 * 设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。
 * 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
 * 输入：prices = [1,2,3,4,5]
 * 输出：4
 * 提示：
 * 1 <= prices.length <= 105
 * 0 <= prices[i] <= 105
 * @since 2022 - 10 - 22 - 22:11
 */
public class _123买卖股票的最佳时机3 {
    public static void main(String[] args) {
        int[] prices = new int[]{1, 2, 3, 4, 5};
        System.out.println(new Solution123().maxProfit(prices));
    }
}
class Solution123{
    public int maxProfit(int[] prices) {
        /*
        对于每一天有5种状态：
        1.不进行任何操作（不需要考虑）
        2.第一次买入
        3.第一次卖出
        4.第二次买入
        5.第二次卖出
        同一天买入并卖出收益为0，对解题没有影响。
         */
        int[] dp = new int[]{-prices[0], 0, -prices[0], 0};//dp[i]表示 i 转态下的最大收益
        for(int i = 1; i < prices.length; i++){
            dp[0] = Math.max(dp[0], -prices[i]);
            dp[1] = Math.max(dp[1], dp[0] + prices[i]);
            dp[2] = Math.max(dp[2], dp[1]-prices[i]);
            dp[3] = Math.max(dp[3], dp[2] + prices[i]);
        }
        return dp[3];
    }
}
